"""lc695: max area of island."""
import os
from typing import List


class Solution:
    def __init__(self):
        ...

    def max_area_of_island(self, world_map: List[List]) -> int:
        """max_area_of_island.

        Args:
            world_map (List[List]): world_map

        Returns:
            int:
        """
        if world_map == [] or world_map[0] == []:
            return 0
        max_area = 0
        for i in range(len(world_map)):
            for j in range(len(world_map[0])):
                if world_map[i][j] == 1:
                    max_area = max(max_area, self.dfs(world_map, i, j))
        return max_area

    def dfs(self, world_map: List[List], i: int, j: int) -> int:
        if world_map[i][j] == 0:
            return 0
        world_map[i][j] = 0
        area = 1
        max_i = len(world_map)
        max_j = len(world_map[0])
        for tmp_i, tmp_j in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= tmp_i < max_i and 0 <= tmp_j < max_j:
                area += self.dfs(world_map, tmp_i, tmp_j)
        return area


if __name__ == "__main__":
    world_map = [
        [1, 0, 1, 1, 0, 1, 0, 1],
        [1, 0, 1, 1, 0, 1, 1, 1],
        [0, 0, 0, 0, 0, 0, 0, 1],
    ]
    a = Solution()
    print(a.max_area_of_island(world_map))
